9631. Соревнования последовательностей

Завтра Зия примет участие в соревновании последовательностей. Число x ≥ 0 называется вершиной некоторой последовательности, если последовательность 1, 2, 3, ..., x – 1, x, x – 1, ..., 3, 2, 1 является подпоследовательностью данной последовательности. Силой каждой последовательности считается ее наибольшая вершина.

Завтра все студенты пойдут на соревнование и победителем станет обладатель сильнейшей последовательности. Зия имеет последовательность a₁, a₂, a₃, ..., a_n. Он хочет завладеть системой оценки соревнования и удалить из нее последовательности с большей силой, чем у него. Однако Зия не знает силу собственной последовательности, но очень хочет победить. Помогите ему определить силу собственной последовательности.

Вход. В первой строке задано количество n (1 ≤ n ≤ 10⁵) чисел в последовательности Зии. В следующей строке записаны n целых чисел a_i (1 ≤ a_i ≤ 10⁵) – элементы последовательности.

Выход. Выведите одно число – силу данной последовательности.

Пример входа 1	Пример выхода 1
2 2 10	0
Пример входа 2	Пример выхода 2
3 1 2 3	1
Пример входа 3	Пример выхода 3
5 1 10 2 3 1	2

РЕШЕНИЕ

два указателя

Анализ алгоритма

Пусть v – входной массив чисел. Инициализируем указатели i = 0 на начало массива и j = n – 1 на конец массива. В переменной k будем подсчитывать силу последовательности. Изначально установим k = 1.

Пока указатели i и j не встретятся, выполняем следующие действия:

· Сдвигаем указатель i на одну позицию вправо, если он не указывает на число k;

· Сдвигаем указатель j на одну позицию влево, если он не указывает на число k;

· Если оба указателя указывают на число k, увеличиваем k на единицу и сдвигаем каждый из указателей на одну позицию в соответствующем направлении;

После завершения работы алгоритма ответом будет значение k – 1.

Пример

Рассмотрим второй тест. Инициализируем указатели. Двигаем указатель i вправо, а j влево пока они не будут указывать на число 1.

Двигаем указатель i вправо, а j влево, пока они не будут указывать на число 2.

Указатели встретились, останавливаем алгоритм. Ответом будет значение k = 2.

Реализация алгоритма

Читаем входные данные.

scanf("%d", &n);

v.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &v[i]);

Установим указатели на начало и конец массива v.

int i = 0, j = v.size() - 1;

В переменной k подсчитываем силу последовательности.

k = 1;

while (i <= j)

{

Указатель i двигаем вправо пока не встретится число k.

if (v[i] != k) i++;

Указатель j двигаем влево пока не встретится число k.

if (v[j] != k) j--;

Если оба указателя указывают на число k, то увеличиваем k на единицу.

if (v[i] == k && v[j] == k) k++;

}

Выводим ответ.

printf("%d\n", k - 1);

Python реализация

Читаем входные данные.

n = int(input())

v = list(map(int, input().split()))

Установим указатели на начало и конец списка v.

i, j = 0, len(v) – 1

В переменной k подсчитываем силу последовательности.

k = 1

while i <= j:

Указатель i двигаем вправо пока не встретится число k.

if v[i] != k:

i += 1

Указатель j двигаем влево пока не встретится число k.

if v[j] != k:

j -= 1

Если оба указателя указывают на число k, то увеличиваем k на единицу.

if v[i] == k and v[j] == k:

k += 1

Выводим ответ.

print(k - 1)